import java.util.LinkedList;
import java.util.Queue;

public class PathSum2 {
    /**
     * 给你二叉树的根节点root 和一个表示目标和的整数targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum 。如果存在，返回 true ；否则，返回 false 。
     * 叶子节点 是指没有子节点的节点。
     * 链接：https://leetcode-cn.com/problems/path-sum
     * @param root
     * @param targetSum
     * @return
     * 解题思路：广度优先遍历
     * 遍历出每条路径 然后计算是否符合条件
     */

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root==null)
            return false;
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while (!queNode.isEmpty()){
            TreeNode now = queNode.poll();
            int temp = queVal.poll();
            if (now.left==null&&now.right==null){
                if (temp==targetSum)
                    return true;
                continue;
            }
            if (now.left!=null){
                queNode.offer(now.left);
                queVal.offer(now.left.val+temp);
            }
            if (now.right!=null){
                queNode.offer(now.right);
                queVal.offer(now.right.val+temp);
            }

        }


        return false;


    }

    public static void main(String[] args) {

    }
}
